/**
 * <p>Suffix Tree and Suffix Array.</p>
 *
 * <p>Suffix tree of string S is a compressed trie of all suffixes of S. Suffix array is a different representation
 * of suffix tree that allows all the operations that suffix tree can do. Unlike suffix tree where data is stored
 * in node and edge in a trie, suffix array store information in arrays that
 * allow more efficient spaces. Most of the time when we do operations in suffix array, we should think about the
 * corresponding suffix tree.</p>
 *
 * <p>Suffix tree can help solve a lot of interesting problems efficiently. However, the space required is a lot more
 * than suffix array. Even though space required for suffix tree is $O(n)$, the constant factor is higher than
 * suffix array. Therefore a lot of effort is spent to study suffix array. Another argument against suffix tree is
 * that building suffix tree in linear time $O(n)$ can be a bit complicated. However, to build suffix array to match
 * suffix tree capability can even be more complicated because you need to augment the suffix array with LCP array,
 * child table and suffix link table which will be discussed later.</p>
 *
 * <p>Let's take one example: banana$.</p>
 *
 * <p>The suffix tree (or compressed suffix trie) will look something like this:</p>
 *
 * <pre>
 *  suffix tree:  ┬ ¥ 6
 *                ├ a ┬ ¥ 5
 *                │   └ na ┬ ¥ 3
 *                │        └ na¥ 1
 *                ├ banana¥ 0
 *                └ na ┬ ¥ 4
 *                     └ na¥ 2
 *
 *
 *                ┌──┬──┴─┬──┐
 *                ¥  a    b  n
 *                6 ┌┴─┐  a  a
 *                  ¥  n  n ┌┴┐
 *                  5  a  a ¥ n
 *                    ┌┴┐ n 4 a
 *                    ¥ n a   ¥
 *                    3 a ¥   2
 *                      ¥ 0
 *                      1
 *
 *            i:  0 1 2 3 4 5 6
 *            S:  b a n a n a ¥
 *
 * suffix array:  6 5 3 1 0 4 2
 *          lcp:  - 0 1 3 0 0 2
 *       suffix:  ¥ a a a b n n
 *                  ¥ n n a a a
 *                    a a n ¥ n
 *                    ¥ n a   a
 *                      a n   ¥
 *                      ¥ a
 *                        ¥
 *
 * lcp interval:
 *
 *
 *
 * </pre>
 *
 *
 *
 *
 *
 *
 * @author Trung Phan
 * @see <p>Kasai et. al. (2001) Linear-time longest-common-prefix computation in suffix arrays and its applications</p>
 *      <p>Abouelhoda et. al. (2004) Replacing suffix trees with enhanced suffix arrays</p>
 */
package net.tp.algo.suffix;